接龙|终点_动态规划：空间优化技巧以及接龙型动态规划

篇首语：本文由编程笔记#小编为大家整理，主要介绍了动态规划：空间优化技巧以及接龙型动态规划相关的知识，希望对你有一定的参考价值。

空间优化方法

滚动数组

如果状态依赖关系只在相邻的几层之间&＃xff0c;则可以使用滚动数组进行优化
滚动数组可以让空间复杂度降维

坐标型动态规划使用滚动数组

数字三角形的状态转移方程为
dp[i][j] &＃61; min(dp[i - 1][j], dp[i - 1][j - 1]) &＃43; A[i][j]

滚动数组优化之后为
dp[i % 2][j] &＃61; min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1]) &＃43; A[i][j]

因为每一步只与他的前一步有关&＃xff0c;所以前面的数组我们可以重复使用&＃xff0c;而不需要开辟新的空间。

随着滚动数组优化&＃xff0c;我们需要改变的地方&＃xff1a;

//原来的版本&＃xff0c;详情请看动态规划入门&＃xff1a;
public int minimumTotal(int[][] triangle)
if (triangle &＃61;&＃61; null || triangle.length &＃61;&＃61; 0)
return -1;

if (triangle[0] &＃61;&＃61; null || triangle[0].length &＃61;&＃61; 0)
return -1;


int n &＃61; triangle.length;
int[][] f &＃61; new int[n][n];

// initialize: 三角形的左边和右边要初始化
// 因为他们分别没有左上角和右上角的点
f[0][0] &＃61; triangle[0][0];
for (int i &＃61; 1; i < n; i&＃43;&＃43;)
f[i][0] &＃61; f[i - 1][0] &＃43; triangle[i][0];
f[i][i] &＃61; f[i - 1][i - 1] &＃43; triangle[i][i];


// function: f[i][j] &＃61; Math.min(f[i - 1][j], f[i - 1][j - 1]) &＃43; triangle[i][j];
for (int i &＃61; 1; i < n; i&＃43;&＃43;)
for (int j &＃61; 1; j < i; j&＃43;&＃43;)
f[i][j] &＃61; Math.min(f[i - 1][j], f[i - 1][j - 1]) &＃43; triangle[i][j];


// answer: 最后一层的任意位置都可以是路径的终点
int best &＃61; f[n - 1][0];
for (int i &＃61; 1; i < n; i&＃43;&＃43;)
best &＃61; Math.min(best, f[n - 1][i]);

return best;

//滚动数组版本&＃xff1a;
public int minimumTotal(int[][] triangle)
if (triangle &＃61;&＃61; null || triangle.length &＃61;&＃61; 0)
return -1;

if (triangle[0] &＃61;&＃61; null || triangle[0].length &＃61;&＃61; 0)
return -1;


int n &＃61; triangle.length;
//空间负责度进行了降纬 n &＃61;> 2
int[][] f &＃61; new int[2][n];

f[0][0] &＃61; triangle[0][0];
// 因为数组空间不能够直接初始化&＃xff0c;我们需要在动态的过程中初始化
for (int i &＃61; 1; i < n; i&＃43;&＃43;)
f[i % 2][0] &＃61; f[(i - 1) % 2][0] &＃43; triangle[i][0];
f[i % 2][i] &＃61; f[(i - 1) % 2][i - 1] &＃43; triangle[i][i];
for (int j &＃61; 1; j < i; j&＃43;&＃43;)
f[i % 2][j] &＃61; min(f[(i - 1) % 2][j], f[(i - 1) % 2][j - 1]) &＃43; triangle[i][j]


// answer: 最后一层的任意位置都可以是路径的终点
int best &＃61; f[(i - 1) % 2][0];
for (int i &＃61; 1; i < n; i&＃43;&＃43;)
best &＃61; Math.min(best, f[(i - 1) % 2][i]);

return best;



从上面的不同的两个版本我们可以知道最大的区别在于初始化&＃xff0c;因为数组空间不能够直接初始化&＃xff0c;所以我们需要在动态的过程中初始化。

那么能否两个维度一起滚动呢?
dp[i][j] &＃61; min(dp[i - 1][j], dp[i - 1][j - 1]) &＃43; A[i][j] &＃61;>
dp[i % 2][j % 2] &＃61; min(dp[(i - 1) % 2][j % 2], dp[(i - 1) % 2][(j - 1) % 2]) &＃43; A[i][j]

不可以&＃xff0c;因为j不是全局单调递增的&＃xff0c;所以他的数据需要被保存&＃xff0c;而 i 是全局单调递增的。

所以我们可以得出&＃xff0c;滚动数组只可以滚动一个维度&＃xff0c;不能滚动两个维度。

实例&＃xff1a;
斐波那契数列

class Solution
public int fib(int n)
int[] dp &＃61; new int[3];
dp[0%3] &＃61; 0;
dp[1%3] &＃61; 1;
for(int i &＃61; 2 ; i <&＃61; n; i&＃43;&＃43;)
dp[i % 3] &＃61; (dp[(i - 1) % 3] &＃43; dp[(i - 2) % 3]) % 1000000007;


return dp[n%3];




总结&＃xff1a;

• 滚动数组滚动的是第一重循环的变量&＃xff0c;而不是第二重甚至第三重
• 滚动数组也只能滚一个维度
• 不能两个维度一起滚动

接龙型动态规划

属于“坐标型”动态规划的一种 题型一般是告诉你一个接龙规则&＃xff0c;让你找最长的龙

经典例题&＃xff1a;
LeetCode 300. 最长递增子序列

给你一个整数数组 nums &＃xff0c;找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列&＃xff0c;删除&＃xff08;或不删除&＃xff09;数组中的元素而不改变其余元素的顺序。例如&＃xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

例子1:
输入&＃xff1a;nums &＃61; [10,9,2,5,3,7,101,18]
输出&＃xff1a;4
解释&＃xff1a;最长递增子序列是 [2,3,7,101]&＃xff0c;因此长度为 4 。


利用动规四要素分析&＃xff1a;

state:
dp[i] 表示以第 i 个数为龙尾的最长的龙有多长
function:
dp[i] &＃61; maxdp[j] &＃43; 1, j < i && nums[j] < nums[i]
initialization://每个位置都可以是龙头
dp[0..n-1] &＃61; 1
answer:
maxdp[0..n-1]


Follow up: 求具体的方法

倒推法
记录每个状态的最优值是从哪个前继状态来的 通常需要一个和状态数组同样维度的数组 prev[i] 记录 使得 dp[i] 获得最优值的那个 j 是谁 j 是方程 dp[i] &＃61; maxdp[j] &＃43; 1 里的j

最长上升连续子序列 II
描述&＃xff1a;
给定一个整数矩阵. 找出矩阵中的最长连续上升子序列, 返回它的长度. 最长连续上升子序列可以从任意位置开始, 向上/下/左/右移动.

输入:
[
[1, 2, 3, 4, 5],
[16,17,24,23,6],
[15,18,25,22,7],
[14,19,20,21,8],
[13,12,11,10,9]
]
输出: 25
解释: 1 -> 2 -> 3 -> 4 -> 5 -> ... -> 25 (由外向内螺旋)


LeetCode 368.最大整除子集

描述&＃xff1a;

给出一个由无重复的正整数组成的集合&＃xff0c;找出其中最大的整除子集&＃xff0c;子集中任意一对 (Si&＃xff0c;Sj) 都要满足&＃xff1a;Si % Sj &＃61; 0 或 Sj % Si &＃61; 0。

如果有多个目标子集&＃xff0c;返回其中任何一个均可。

示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)


class Solution
public List<Integer> largestDivisibleSubset(int[] nums)
if (nums &＃61;&＃61; null || nums.length &＃61;&＃61; 0)
return new ArrayList();


Arrays.sort(nums);
int n &＃61; nums.length;
HashMap<Integer, Integer> dp &＃61; new HashMap();
HashMap<Integer, Integer> prev &＃61; new HashMap();

for (int i &＃61; 0; i < n; i&＃43;&＃43;)
dp.put(nums[i], 1);
prev.put(nums[i], -1);


int lastNum &＃61; nums[0];
for (int i &＃61; 0; i < n; i&＃43;&＃43;)
int num &＃61; nums[i];
for (Integer factor : getFactors(num))
if (!dp.containsKey(factor))
continue;

if (dp.get(num) < dp.get(factor) &＃43; 1)
dp.put(num, dp.get(factor) &＃43; 1);
prev.put(num, factor);


if (dp.get(num) > dp.get(lastNum))
lastNum &＃61; num;



return getPath(prev, lastNum);


private List<Integer> getPath(HashMap<Integer, Integer> prev, int lastNum)
List<Integer> path &＃61; new ArrayList();
while (lastNum !&＃61; -1)
path.add(lastNum);
lastNum &＃61; prev.get(lastNum);

Collections.reverse(path);
return path;


private List<Integer> getFactors(int num)
List<Integer> factors &＃61; new ArrayList();
if (num &＃61;&＃61; 1)
return factors;

int factor &＃61; 1;
while (factor * factor <&＃61; num)
if (num % factor &＃61;&＃61; 0)
factors.add(factor);
if (factor !&＃61; 1 && num / factor !&＃61; factor)
factors.add(num / factor);


factor&＃43;&＃43;;

return factors;